package solution.s_31;

/**
 * 解题思路：
 *     根据题目就会发现。
 *     其实只要从后向前找，找到 i，满足 nums[i] < nums[i + 1]。
 *     假如找不到这个位置，说明是一个降序数组，直接进行数组反转就行。
 *     假如找到 i 的位置，然后从后向前遍历，找到比 j 的位置，j 满足 nums[j] > nums[i]，两个元素进行交换。
 *     此时会发现 nums[i+1,nums.length) 是一个降序数组。
 *     将 nums[i+1,nums.length) 转换为升序数组即可。
 */
public class Solution20201026 {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) { return; }

        // 找到满足 nums[i] > nums[i+1] 的 i 的位置。
        int targetIndex = -1;
        for (int i = nums.length - 2; i >= 0; i --) {
            if (nums[i] < nums[i + 1]) {
                targetIndex = i;
                break;
            }
        }

        // 没有找到 i 的位置，表明数组是降序排列，有序的，直接进行数组反转。
        if (targetIndex == -1) {
            for (int i = 0; i < nums.length / 2; i ++) {
                int temp = nums[i];
                nums[i] = nums[nums.length - 1 - i];
                nums[nums.length - 1 - i] = temp;
            }
            return;
        }

        // 找到 i 的位置，找到 (i,nums.length) 中比 i 大的元素，两个元素进行位置。
        for (int i = nums.length - 1; i > targetIndex; i --) {
            if (nums[i]  > nums[targetIndex]) {
                int temp = nums[i];
                nums[i] = nums[targetIndex];
                nums[targetIndex] = temp;
                break;
            }
        }

        // 然后 nums[targetIndex+1, nums.length) 一定是降序，然后将其改为升序。
        for (int i = 1; i <= (nums.length - 1 - targetIndex) / 2; i ++) {
            int temp = nums[targetIndex + i];
            nums[targetIndex + i] = nums[nums.length - i];
            nums[nums.length - i] = temp;
        }
    }
}
